home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / hash / RCS / Hash.man,v < prev    next >
Text File  |  1988-12-30  |  3KB  |  75 lines
  1. head     1.1;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @@;
  7.  
  8.  
  9. 1.1
  10. date     88.12.30.15.05.14;  author ouster;  state Exp;
  11. branches ;
  12. next     ;
  13.  
  14.  
  15. desc
  16. @@
  17.  
  18.  
  19.  
  20. 1.1
  21. log
  22. @Initial revision
  23. @
  24. text
  25. @' $Header: Io,v 1.4 86/06/26 10:05:35 ouster Exp $ SPRITE (Berkeley)
  26. .so \*(]ltmac.sprite
  27. .HS Hash lib
  28. .BS
  29. .SH NAME
  30. Hash \- overview of routines to manipulate hash tables
  31. .BE
  32.  
  33. .PP
  34. The Hash_ routines provide mechanisms for manipulating hash
  35. tables.  A hash table is a data structure that stores any
  36. number of entries, each of which is a <key, value> pair.
  37. Given the key for a particular entry, the
  38. Hash_ routines can very quickly find the entry (and hence the
  39. associated value).  There can be at most one entry with a given
  40. key in a hash table at a time, but many entries may have the
  41. same value.
  42. .PP
  43. This library provides two unusual features.  First, hash tables
  44. can grow gracefully.  In most hash table implementations
  45. the  number of buckets in the table is fixed;  if the number of
  46. entries in the table becomes substantially larger than the number
  47. of buckets, the performance of the table degrades.  In contrast,
  48. this implementation automatically re-allocates the bucket memory
  49. as the table grows.  As a result, hash tables can become arbitrarily
  50. large without overloading the buckets.  An initial number of buckets
  51. may be provided when tables are initialized, but it will change later
  52. (automatically) if necessary to guarantee efficient operation.
  53. .PP
  54. The second unusual feature of the Hash_ routines is that they allow
  55. keys to be expressed in several forms.  Keys may either be variable-length
  56. NULL-terminated strings, or single-word values, or multi-word records
  57. of any length (in the latter case, all keys in the table must be the
  58. same length).  See Hash_InitTable for deatils on the different key types.
  59. .PP
  60. Hash tables are initialized by calling \fBHash_InitTable\fR.  New entries
  61. are added with \fBHash_CreateEntry\fR, and existing entries may be located
  62. with either \fBHash_CreateEntry\fR or \fBHash_FindEntry\fR.  The values stored
  63. in entries are manipulated with \fBHash_GetValue\fR and Hash_SetValue
  64. (values may be arbitrary one-word values; they are stored in entries
  65. and retrieved from them using the type ``ClientData'').  An entry
  66. can be deleted from the table by calling \fBHash_DeleteEntry\fR;  the entire
  67. table can be released by calling \fBHash_DeleteTable\fR.  \fBHash_EnumFirst\fR
  68. and \fBHash_EnumNext\fR provide a facility for stepping through all the
  69. entries in a table.  Finally, \fBHash_PrintStats\fR can be invoked to print
  70. out some usage information about a hash table.
  71.  
  72. .SH KEYWORDS
  73. hash table, key, value
  74. @
  75.